#
# @lc app=leetcode.cn id=53 lang=python
#
# [53] 最大子数组和
#

# @lc code=start
## 贪心算法
# class Solution(object):
#     def maxSubArray(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: int
#         """
#         sum_result = float('-inf')
#         cur = 0
#         for i in range(len(nums)):
#             cur += nums[i]
#             if cur > sum_result:
#                 sum_result = cur

#             if cur <= 0:
#                 cur = 0
#         return sum_result

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [0] * (len(nums))
        result = nums[0]
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(0, dp[i-1]) + nums[i]
            result = max(dp[i], result)
        return result
        
# @lc code=end

